package com.levi.recursion;

/**
 * @author shentong
 * @date 2021/8/30 16:51
 * @Description 八皇后问题
 * 用一维数组实现八皇后问题
 * arr[8] = {4,3,6,8,7,1,4,2}
 * arr[i] = n   i表示行的下标，n表示列的下标   arr[i] = n表示把皇后放在棋盘的第i+1行第n+1列的位置，因为下标都是从0开始
 */
public class EightQueue {
    //创建一个长度为8的一维数组
    int max = 8;
    int[] arr = new int[max];
    private static int count = 0;
    private static int judgeCount = 0;
    public static void main(String[] args) {
        EightQueue eightQueue = new EightQueue();
        eightQueue.check(0);
        System.out.printf("八皇后问题一共有%d种解法\n",count);
        System.out.printf("一共判断了%d次冲突\n", judgeCount);
    }

    /**
     * 摆放皇后
     * 特别注意:check是每一次递归时，进入check都有for循环  for (int i = 0; i < max; i++)，因此会有回溯
     * @param n
     */
    public void check(int n) {
        //如果n == 8表示正要准备放第9个皇后，这时候打印，然后退出程序
        if (n == max) {
            print();
            return;
        }
        for (int i = 0; i < max; i++) {
            //先让皇后放在第一列，然后判断是否冲突
            arr[n] = i;
            //如果不冲突就开始递归放置下一行个皇后
            if (judge(n)) {
                check(n + 1);
            }
            //如果冲突了，会在for循环冲执行i++，放到第二列，如果还冲突就放到第三列.....，以此类推，知道不冲突为止
        }
    }
    /**
     * 判断新摆放的皇后有没有与之前放的皇后冲突(在同一行，或者同一列，或者同一斜线上的都视为冲突),有冲突过了返回false，没有冲突返回true
     * 逐个与之前放的皇后进行比较，所以这里要循环遍历
     * @param n
     * @return
     */
    public boolean judge(int n) {
        judgeCount++;
        for (int i = 0; i < n; i++) {
            //arr[i] == arr[n]  表示在同一列
            //FIXME Math.abs(n - i) == Math.abs(arr[i] - arr[n]) 表示横坐标和纵坐标相差的距离相等，即斜率为+1或者-1，取绝对值进行比较
            if (arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[i] - arr[n])) {
                return false;
            }
        }
        return true;
    }

    /**
     * 打印这个一维数组arr
     */
    public void print() {
        count++;
        for (int i = 0; i < max; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }

}
